package chapter03_binaryTree;

/**
 * 描述：
 * 统计完全二叉树的结点数，时间复杂度可以抵御O(N)
 * 1）首先求出完全二叉树的高度，完全二叉树的高度可以通过一直向左遍历得到，如果是空树则返回0
 * 2）递归过程bs(node, l, h)，node代表当前子树的根结点，l代表当前node来到整颗数的哪一层，h代表整颗数的高
 * 从根结点开始查看右子树的的最左结点是否到达h层：
 * 如果到达h层，则说明node的左子树为满二叉树，层级为h-l，一颗层数为h-l的满二叉树结点数为2^h-l - 1
 * 如果没有到达h层，则说明node的右子树是层级为h-l-1的满二叉树
 *
 * @author hl
 * @date 2021/6/2 16:55
 */
public class NodeNum {
    public static void main(String[] args) {
        System.out.println(1 << 1);
        System.out.println(Math.pow(2, 0));
    }
    public int nodeNum(Node head) {
        if (head == null) {
            return 0;
        }
        return bs(head, 1, mostLeftLevel(head, 1));
    }

    private int bs(Node head, int l, int h) {
        if (l == h) {
            return 1;
        }
        if (mostLeftLevel(head.right, l + 1) == h) {
            return (1 << (h - l)) + 1 + bs(head.right, l + 1, h);
        }else{
            return (1 << (h - l - 1)) + 1 + bs(head.left, l + 1, h);
        }
    }

    private int mostLeftLevel(Node head, int l) {
        while (head != null) {
            l++;
            head = head.left;
        }
        return l - 1;
    }


}
